'''
Created on May 20, 2009

@author: sternron
'''
import graph
from cliques.cliqueFinder import cliqueFinder
import time
import logging 

class cliqueAlgorithm():
    '''
    base class for clique search algorithms
    '''

    def __init__(self):
        '''
        Constructor
        '''
        self.clique_finder = cliqueFinder()

    def __str__(self):
        return "cliqueAlgorithm"

    def initial_status(self):
        print "%s - Start %d-clique search in graph(%d) from node %s with alg.%s" \
            % (time.ctime(),self.k,len(self.unknown_graph.nodes()),self.start_node, self)

    def setup(self, unknown_graph, k, start_node):
        '''
        Setup the relevant data structures
        '''
        self.unknown_graph = unknown_graph
        self.k = k
        self.done = False
        self.start_node = start_node
        self.ckg = graph.graph()
        self.ckg.add_node(start_node)
        self.clique_finder.setup(self.ckg)
        self.generated=[start_node]
        self.expanded=[]
        self.iteration = 0
        self.current_node = self.start_node
        
    def run(self, unknown_graph,k,start_node):
        self.setup(unknown_graph, k, start_node)
        
        # Continue search until a clique was found or entire graph was searched
        while self.halt()==False:
            self.step()
 
    def halt(self):
        return self.clique_found()==True or len(self.generated)==0
    
    def clique_found(self):
        self.done = self.clique_finder.has_clique(self.k-1,self.ckg.neighbors(self.current_node))
        return self.done
        
    def step(self):
        self.current_node = self.choose_node()
        logging.debug("Chosen node %s for expansion" % self.current_node)       
        self.expand(self.current_node)
        self.iteration=self.iteration+1

    def status(self):
        print "[%d]expanding %s with %d neighbors" % (self.iteration,self.current_node,len(self.unknown_graph.neighbors(self.current_node)))
        if self.done: print "Found!"

    def expand(self, node):
        # Update CKG, expanded, generated
        self.generated.remove(node)
        self.expanded.insert(0,node)
        for neighbor in self.unknown_graph.neighbors(node):
            if neighbor not in self.expanded:
                self.generate(node, neighbor)

    def generate(self,parent,new_node):
        ''' Generate a node '''
        if new_node not in self.generated:
            self.generated.insert(0,new_node)
            self.ckg.add_node(new_node)
        if parent is not None:
            self.ckg.add_edge(parent,new_node) 

    def statistics(self):
        return []
    def get_cost(self):
        return len(self.expanded)
        
    def choose_node(self):
        abstract
        
    def output_clique(self):
        return self.clique_finder.find_clique(self.k,self.ckg)
        